package com.explorati.dongtaiguihua.LeetCode343;

import java.util.Arrays;

/**
 * 动态规划解法
 * 
 * @author explorati
 *
 */
public class Solution1 {
	private int max(int a, int b, int c) {
		return Math.max(a, Math.max(b, c));
	}

	public int integerBreak(int n) {
		assert (n >= 2);

		// memo[i]表示将数字i分割(至少分割成两部分)后的到的最大乘积
		int[] memo = new int[n + 1];
		Arrays.fill(memo, -1);

		memo[1] = 1;
		for (int i = 2; i <= n; i++) {
			// 求解memo[i]
			for (int j = 1; j <= i - 1; j++) {
				// j + (i - j)
				memo[i] = max(memo[i], j * (i - j), j * memo[i - j]);
			}
		}
		return memo[n];
	}
}
